package com.qjc.demo.algorithm;

import java.util.Arrays;

/**
 * @ClassName: MergeSortArray
 * @Description: 合并有序数组：两个有序数组nums1和nums2，将nums2合并到nums1中，是nums1成为一个有序数组
 * 初始化nums1和nums2的元素数量分别为m和n。假设nums1的空间大小等于m+n，这样他们就有足够的空间保存来自nums2的元素。
 * @Author: qjc
 * @Date: 2022/5/6 11:29 AM
 */
public class MergeSortArray {

    // 时间复杂度是O(nlog n) 空间复杂度是O(1)
    public static int[] normal(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
        return nums1;
    }

    // 使用临时数组，让空间换时间
    public static int[] betterMerge(int[] nums1, int m, int[] nums2, int n) {
        // 创建一个临时数组，将nums1的有效数字复制进去
        int[] nums1_copy = new int[m];
        System.arraycopy(nums1, 0, nums1_copy, 0, m);

        int p1_copy = 0; // temp的指针
        int p1 = 0; // nums1的指针
        int p2 = 0; // nums2的指针
        while (p1_copy < m && p2 < n) {
            nums1[p1++] = nums1_copy[p1_copy] < nums2[p2] ? nums1_copy[p1_copy++] : nums2[p2++];
        }
        if (p1_copy < m) {
            // 说明temp还没有遍历完，直接将剩余的拷贝到nums1中
            System.arraycopy(nums1_copy, p1_copy, nums1, p1_copy + p2, m + n - p1_copy - p2);
        }
        if (p2 < n) {
            // 说明nums2还没有遍历完，直接将剩余的拷贝到nums1中
            System.arraycopy(nums2, p2, nums1, p1_copy + p2, m + n - p1_copy - p2);
        }
        return nums1;
    }

    // 不是用临时数组，直接使用nums1，不过指针是从后面开始比较
    public static int[] bestMerge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;// nums1数组中有效数字的尾部
        int p2 = n - 1;// nums2数组的尾部
        int p = m + n - 1;// nums1数组的尾部
        while (p1 >= 0 && p2 >= 0) {
            nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
        }
        // 将nums2剩余的拷贝到nums1中
        System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
        return nums1;
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 3, 5, 7, 9, 0, 0, 0, 0};
        int[] nums2 = new int[]{2, 4, 6, 8};
//        System.out.println(Arrays.toString(normal(nums1, 5, nums2, 4)));
//        System.out.println(Arrays.toString(betterMerge(nums1, 5, nums2, 4)));
        System.out.println(Arrays.toString(bestMerge(nums1, 5, nums2, 4)));
    }

}
